package tss.util;

/**
 * Vector timestamps are used for implementing Lamport's
 * "happens-before" relation, '->', between events in order to
 * realize logical time in a process group in a distributed system
 * 
 * <p>The happens-before relation may be defined in the following way:
 * 
 * <ol>
 * <li> a[p] -> b[p], i.e., if a and b are events that happen in a 
 * 					process p, we can order the events
 * <li> send(m)[p] -> receive(m)[q], i.e., the send of a message by process p 
 *                                 happens before it is received by q
 * </ol>
 * 
 * <p>(Notice that we distinguish the events 'receive' and 'deliver'. Receive
 * means that a message is received, deliver means that a received message
 * is handed over to an application program. This is important to implement
 * reliable communication)
 * 
 * <p>Each process in the group maintains its own vector timestamp having 
 * logical clocks (i.e., integers) of the processes in the group as entries. 
 * Logical clocks are indexed by process id. The vector timestamp of a process 
 * is sent with all messages it sends 
 * 
 * <p>Below we will write [x0, ..., xn] as the representation of a 
 * vector timestamp, each entry of the vector being a logical clock
 * 
 * <p>The following must be observed by implementations and uses of 
 * vector timestamps:
 * 
 * <ol>
 * <li> a vector timestamp is initalized to all zero entries
 * <li> when a process experiences an event (internal, send, receive events)
 *    it increments its own clock entry by one
 * <li> a process only delivers a message if it can deduce that it is not missing
 *    any messages with respect to '->, cf. 'canDeliver'
 *    If a message is delivered to a process, the process sets the 
 *    clock entries in its vector timestamp to the maximum of the
 *    timestamps of its entries and the entries from the vector received
 * <li> when a message is delivered in a process, the vector timestamp of
 *    the process is set to the maximum of the vector timestamp of the message
 *    and the vector timestamp of the process cf. 'max' below
 *</ol>
 * <p>If this is obeyed the following is true for events a, b and processes p, q:
 * 
 * <pre>
 *    a[p] -> b[q] <=> VT(a)[p] < VT(b)[q]
 * </pre>
 * here VT(a)[p] is the vector timestamp of p when a happens. 
 * 
 * <p>"T < S", where T and S are vector timestamps, means that each clock entry of T
 * are less than or equals to the corresponding entry of S and that there
 * is at least one entry of T that is strictly smaller than the corresponding
 * entry of S
 *
 * @author Klaus Marius Hansen, klaus.m.hansen@daimi.au.dk
 * 
 */
public interface VectorTimestamp {
	/**
	 * A vector timestamp is owned by a process which has an id
	 * 
	 * @return the id of the owner process
	 */
	public int id();

	/**
	 * Get the current value of the logical clock for a process
	 *
	 * @param id of the process for which the value should
	 * 		     returned. id should be >= 0 and < size()
	 * 
	 * @throws IllegalAmount if id < 0 or id >= size
	 * 
	 * @return this[id] 
	 *  
	 */
	public int get(int id) throws IllegalArgumentException;
	
	/**
	 * Increments the logical clock for this process by 1
	 * All other clocks are left unchanged
	 * 
	 * <p>E.g., if this vector timestamp is [1, 3, 4] and this.id() == 2,
	 * this vector timestamp is [1, 3, 5] after invoking increment
	 * 
	 */
	public void increment();
	
	/**
	 * Set the logical clock entries of this vector timestamp to the maximum
	 * of its logical clocks and other's logical clocks
	 * 
	 * <p>E.g., if this vector timestamp is [2, 5] and other is [1, 6], then
	 * this vector timestamp is [2, 6] after invoking max
	 * 
	 * @param other  a vector timestamp to maximize this vector timestamp
	 *               with respect to

	 * @throws IllegalAmount if other.size() != size() 
	 * 
	 */
	public void max(VectorTimestamp other) throws IllegalArgumentException;

	/**
	 * Get the (constant) number of entries in this VectorTimestamp
	 * 
	 * <p>E.g., if this vector timestamp is [3, 5, 7], size() returns 3 
	 * 
	 * @return number of entries
	 */
	public int size();
	
	/**
	 * A vector timestamp, other, can be delivered to this process if:
	 * 
	 * <pre>
	 *   for 0 <= i < size(), i != other.id(), i != id(): other[i] <= this[i], and
	 *   other[other.id()] == this[other.id()] + 1
	 * </pre>
	 * 
	 * E.g., if this vector timestamp is [3, 4, 7] and id() == 2 then 
	 * canDeliver will return true for ([4, 2, 5], 0) and false for
	 * ([5, 2, 5], 0)
	 * 
	 * @param other a VectorTimestamp to compare this vector timestamp to
	 *        
	 * @throws IllegalArgument  if other is uncomparable to this vector timestamp
	 * 
	 * @return true if other is causally next
	 * 
	 */
	public boolean canDeliver(VectorTimestamp other)
		throws IllegalArgumentException;
}
